package org.example.test;


import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author: lynn
 * @Descript:
 * @date: 2021/3/8 20:23
 * @version: 1.0
 */
public class BestLru<K,V> {
    //LRU HashMap + Node
    private class ListNode<K,V>{
        ListNode pre;
        ListNode next;
        K k;
        V v;
        ListNode(K k,V v){
            this.k=k;
            this.v=v;
        }
    }

    int limit; //lru的长度
    Map<K,ListNode> hashMap;
    ListNode head; //链表头结点
    ListNode end; //链表尾结点
    BestLru(int limit){
        this.limit=limit;
        hashMap=new HashMap<>();
    }

    public V get(K k){
        ListNode tmpNode=hashMap.get(k);
        if (tmpNode==null){
            return null;
        }
        //refresh(ListNode)
        refresh(tmpNode);
        return (V)tmpNode.v;
    }
    public void  put(K k,V v){

        ListNode tmpNode=hashMap.get(k);

        if (tmpNode!=null){
            tmpNode.v=v;
            refresh(tmpNode);
        }else {
            //fixme 没有，加入Node中,逻辑严重错误，当时只是在else里面addNode了
            ListNode targetNode=new ListNode(k,v);
            if (hashMap.size()>=limit){
                hashMap.remove(deleteNode(head));
            }else {
                hashMap.put(k,targetNode);
            }
            addNode(targetNode);
        }
    }


    private void refresh(ListNode node){
        if (node==end){
            return;
        }
        deleteNode(node);
        addNode(node);
    }
    private K deleteNode(ListNode node){
        if(head==null && end==null){ //fixme 漏了
            head=node;
            end=node;
        }
        else if (head==node){
            head=head.next;
            head.pre=null;
        }else if (end==node){
            end=end.pre;
            end.next=null;
        }else {
            node.next.pre=node.pre;
            node.pre.next=node.next;
        }
        return (K)node.k;
    }

    private void addNode(ListNode node){
        if (end!=null){
            end.next=node;
            node.pre=end;
            node.next=null;// fixme
        }
        end=node;
        if (head==null){
            head=node;
        }
    }
    public static void main(String[] args) {
        BestLru<String,Integer> test=new BestLru(3);
        test.put("a",1);
        test.put("b",2);
        test.put("c",3);
        test.put("d",4);
        System.out.println(test.get("a"));
        test.put("b",6);
        System.out.println(test.get("b"));
    }
}
